package pro.softzhang.algo.lc300;

import pro.softzhang.algo.flag.knowledge.KDynamicPlanning;

import java.util.Arrays;

@KDynamicPlanning
public class LC322_CoinChange {
    public static void main(String[] args) {

    }

    static class Solution {
        public int coinChange(int[] coins, int amount) {
            int[] dp = new int[amount + 1];
            Arrays.fill(dp, amount + 1);
            dp[0] = 0;
            for (int coin : coins) {
                for (int j = amount; j >= 1; j--) {
                    for (int k = 1; k * coin <= j; k++) {
                        dp[j] = Math.min(dp[j], dp[j - k * coin] + k);
                    }
                }
            }
            return dp[amount] > amount ? -1 : dp[amount];
        }
    }
}
